import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class BinaryTreeTest_hjl {

    public static void main(String[] args) {
//        Integer[] testData = {1, 2, 3, 4, 5, 6, 7, null, null, null, null, 8, 9, null, null};

        Integer[] testData = {1, 2, 3, 4, 5, null, 6};

        TreeNode treeNode = buildBinaryTree(testData);
        List<Double> result = getAverageOfLevels(treeNode);
        for (int index = 0; index < result.size(); index++) {
            System.out.print(result.get(index) + "  ");
        }
    }

    /**
     * 构建一个二叉树
     *
     * @param dataArray 一个数组
     * @return
     */
    private static TreeNode buildBinaryTree(Integer[] dataArray) {
        int floor = 0, count = 0;
        TreeNode[] treeNodes = new TreeNode[dataArray.length];
        while (dataArray != null && count < dataArray.length) {
            int start = (int) Math.pow(2, floor) - 1;
            int end = (int) Math.pow(2, floor + 1) - 1;
            if (end > dataArray.length) {
                end = dataArray.length;
            }

            for (int index = start; index < end; index++) {
                if (dataArray[index] != null) {
                    treeNodes[index] = new TreeNode(dataArray[index]);
                } else {
                    treeNodes[index] = null;
                }
                if (index > 0) {
                    int parent = (index - 1) / 2;
                    if (parent >= 0) {
                        TreeNode pNode = treeNodes[parent];
                        if (pNode != null) {
                            if (index % 2 == 1) {
                                pNode.left = treeNodes[index];
                            } else {
                                pNode.right = treeNodes[index];
                            }
                        }
                    }
                }
                count++;
            }
            floor++;
        }
        return treeNodes[0];
    }

    /**
     * 获取二叉树每层节点的平均值
     *
     * @param root
     * @return
     */
    private static List<Double> getAverageOfLevels(TreeNode root) {
        LinkedList<TreeNode> treeNodeLinkedList = new LinkedList<>();
        List<Double> res = new ArrayList<>();
        treeNodeLinkedList.offer(root);
        while (!treeNodeLinkedList.isEmpty()) {
            int size = treeNodeLinkedList.size();
            double sum = 0;
            for (int i = 0; i < size; ++i) {
                TreeNode temp = treeNodeLinkedList.poll();
                if (temp.left != null) {
                    treeNodeLinkedList.offer(temp.left);
                }
                if (temp.right != null) {
                    treeNodeLinkedList.offer(temp.right);
                }
                sum += temp.value;
            }
            res.add(sum / size);
        }
        return res;
    }

    public static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }
}
